import java.util.Arrays;

/**
 * 238. 除自身以外数组的乘积
 */
public class Solution_238 {
    /**
     * 方法二：优化方法一的空间复杂度
     * <p>
     * 时间复杂度：O(N)
     * <p>
     * 空间复杂度：O(1)
     */
    public int[] productExceptSelf(int[] nums) {
        int len = nums.length;
        int[] ans = new int[len];

        // left 为该数右边的乘积
        // 因为索引为 '0' 的元素左侧没有元素， 所以 ans[0] = 1
        int left = 1;
        for (int i = 0; i < len; i++) {
            ans[i] = left;
            left = left * nums[i];
        }
        // 此时数组存储的是除去当前元素，左边元素的乘积

        // right 为该数右边的乘积
        int right = 1;
        for (int i = len - 1; i >= 0; i--) {
            ans[i] = ans[i] * right;
            right = right * nums[i];
        }
        return ans;
    }

    /**
     * 方法一：左右乘积列表
     * <p>
     * 时间复杂度：O(N)
     * <p>
     * 空间复杂度：O(N)
     */
    public int[] productExceptSelf1(int[] nums) {
        int len = nums.length;

        // L 和 R 分别表示左右两侧的乘积列表
        int[] L = new int[len];
        int[] R = new int[len];

        int[] ans = new int[len];

        // L[i] 为索引 i 左侧所有元素的乘积
        // 对于索引为 '0' 的元素，因为左侧没有元素，所以 L[0] = 1
        L[0] = 1;
        for (int i = 1; i < len; i++) {
            L[i] = nums[i - 1] * L[i - 1];
        }

        // R[i] 为索引 i 右侧所有元素的乘积
        // 对于索引为 'length-1' 的元素，因为右侧没有元素，所以 R[length-1] = 1
        R[len - 1] = 1;
        for (int i = len - 2; i >= 0; i--) {
            R[i] = nums[i + 1] * R[i + 1];
        }

        // 对于索引 i，除 nums[i] 之外其余各元素的乘积就是左侧所有元素的乘积乘以右侧所有元素的乘积
        for (int i = 0; i < len; i++) {
            ans[i] = L[i] * R[i];
        }
        return ans;
    }

    public static void main(String[] args) {
        Solution_238 solution = new Solution_238();
        int[] nums = { 1, 2, 3, 4 };
        int[] ans = solution.productExceptSelf(nums);
        System.out.println(Arrays.toString(ans));
    }
}
